#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define N 10

int x[N];
int totalvalue = 0;
int bestpresent = 0;

//int MaxValue(vector<int>& weight, vector<int>& value, int capacity, int k, const int n, vector<int>& space) {
//	if (k > n) {
//		
//	}
//}
//
//int main() {
//	int num, capacity;
//	cout << "Please input the num of staff:";
//	cin >> num;
//	vector<int> weight(num);
//	vector<int> value(num);
//	cout << "Please input the weight of every staff:";
//	for (auto& e : weight) cin >> e;
//	cout << "Please input the value of every staff:";
//	for (auto& e : value) cin >> e;
//	cout << "Please input the max weight:";
//	cin >> capacity;
//	return 0;
//}

//int maxValueRec(const vector<int>& weight, const vector<int>& value, int capacity, int k, const int n, vector<int>& space) {
//    // 如果已经考虑完所有物品，返回0，因为我们只关心物品被选中的情况
//    if (k == n) {
//        return 0;
//    }
//
//    // 不选择第k个物品，递归考虑下一个物品
//    int valueWithoutK = maxValueRec(weight, value, capacity, k + 1, n, space);
//
//    // 选择第k个物品，如果当前物品的重量不超过背包的剩余容量
//    int valueWithK;
//    if (weight[k] <= capacity) {
//        // 选择第k个物品，更新背包的剩余容量
//        capacity -= weight[k];
//        // 记录选择第k个物品
//        space[k] = 1;
//        // 递归考虑下一个物品
//        valueWithK = value[k] + maxValueRec(weight, value, capacity, k + 1, n, space);
//        // 回溯，撤销选择第k个物品
//        capacity += weight[k];
//        space[k] = 0;
//    }
//    else {
//        // 如果当前物品的重量超过背包的剩余容量，不能选择它
//        valueWithK = 0;
//    }
//
//    // 返回不选择和选择第k个物品的最大价值
//    return  max(valueWithoutK, valueWithK);
//}
//
//int MaxValue(const vector<int>& weight, const vector<int>& value, int capacity, int k, const int n,  ::vector<int>& space) {
//    // 初始化解空间，所有物品默认不被选择
//    fill(space.begin(), space.end(), 0);
//    // 计算最大价值
//    return maxValueRec(weight, value, capacity, k, n, space);
//}
//
//int main() {
//     vector<int> weight = { 16, 15, 15 }; // 物品的重量
//     vector<int> value = { 45, 25, 25};  // 物品的价值
//    int capacity = 30;                    // 背包的容量
//    int n = weight.size();                 // 物品的数量
//     vector<int> space(n, 0);          // 解空间
//
//    int maxValue = MaxValue(weight, value, capacity, 0, n, space);
//    cout << "The maximum value is: " << maxValue << endl;
//
//    // 打印选择的物品
//     cout << "Items selected: ";
//    for (int i = 0; i < n; ++i) {
//        cout << space[i] << " ";
//    }
//     cout <<  endl;
//
//    return 0;
//}

// 用于记录解空间的全局变量
vector<int> space;

int maxValueRec(const vector<int>& weight, const vector<int>& value, int capacity, int k, const int n) {
    if (k == n) {
        return 0; // 到达最底层，返回0
    }
    int valueWithoutK = maxValueRec(weight, value, capacity, k + 1, n);
    int valueWithK = 0;
    if (weight[k] <= capacity) {
        valueWithK = value[k] + maxValueRec(weight, value, capacity - weight[k], k + 1, n);
    }
    return max(valueWithoutK, valueWithK);
}

int MaxValue(const vector<int>& weight, const vector<int>& value, int capacity, const int n) {
    
    int maxValue = maxValueRec(weight, value, capacity, 0, n);
    return maxValue;
}

//int main() {
//    vector<int> weight = { 2,2,6,5,4 }; // 物品的重量
//    vector<int> value = { 6,3,5,4,6 };  // 物品的价值
//    int capacity = 10;                // 背包的容量
//    int n = weight.size();             // 物品的数量
//
//    int maxValue = MaxValue(weight, value, capacity, n);
//    cout << "The maximum value is: " << maxValue << endl;
//
//    
//    return 0;
//}

int main() {
	int num, capacity;
	cout << "Please input the num of staff:";
	cin >> num;
	vector<int> weight(num);
	vector<int> value(num);
	cout << "Please input the weight of every staff:";
	for (auto& e : weight) cin >> e;
	cout << "Please input the value of every staff:";
	for (auto& e : value) cin >> e;
	cout << "Please input the max weight:";
	cin >> capacity;
    int n = weight.size();             // 物品的数量
    int maxValue = MaxValue(weight, value, capacity, n);
    cout << "The maximum value is: " << maxValue << endl;
	return 0;
}


// function maxValueRec(weight, value, capacity, k, n):
//     if k == n:
//         return 0 // 到达最底层，返回0
//   
//     // 计算不选择第k个物品的最大价值
//     valueWithoutK = maxValueRec(weight, value, capacity, k + 1, n)
//    
//     // 初始化选择第k个物品的价值为0
//     valueWithK = 0
//   
//     // 如果第k个物品的重量小于等于背包容量
//     if weight[k] <= capacity:
//         // 选择第k个物品，并递归计算剩余容量的最大价值
//         valueWithK = value[k] + maxValueRec(weight, value, capacity - weight[k], k + 1, n)
//    
//     // 返回不选择和选择第k个物品的最大价值中的较大者
//     return max(valueWithoutK, valueWithK)
//
// // 主函数调用递归算法计算最大价值
// maxValue = maxValueRec(weight, value, capacity, 0, n)